# 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。 
# 
# 
#  
# 
#  
#  
#  示例 1： 
# 
#  
# 输入：n = 2
# 输出：[0,1,1]
# 解释：
# 0 --> 0
# 1 --> 1
# 2 --> 10
#  
# 
#  示例 2： 
# 
#  
# 输入：n = 5
# 输出：[0,1,1,2,1,2]
# 解释：
# 0 --> 0
# 1 --> 1
# 2 --> 10
# 3 --> 11
# 4 --> 100
# 5 --> 101
#  
# 
#  
# 
#  提示： 
# 
#  
#  0 <= n <= 105 
#  
# 
#  
# 
#  进阶： 
# 
#  
#  很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？ 
#  你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ） 
#  
#  
#  
#  Related Topics 位运算 动态规划 
#  👍 803 👎 0


from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def countBits(self, n: int) -> List[int]:
        bits = [0]
        for i in range(1, n+1):
            bits.append(bits[i >> 1] + (i & 1))
        return bits



# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)

# 比特位计数
# x & (x - 1), 可以将最后一个1变成0
# 不断操作, 累加, 直到变成0
# y 是 2 的 整数幂, 当且仅当 y & (y -1) == 0
# 最低有效位, 之前算过的不重复急死安
# bit[x] = bit[x/2] + 除以2的余数
# bit[x] = bit[x >> 1] + (x & 1)
#     bits = [0]
#     for i in range(1, n + 1):
#         bits.append(bits[i >> 1] + (i & 1))
#     return bits

# 我的解法:
#     def countBits(self, n: int) -> List[int]:
#         def count(x: int):
#             distance = 0
#             while x != 0:
#                 if x & 1 == 1:
#                     distance += 1
#                 x = x >> 1
#             return distance
#         return [count(i) for i in range(0, n + 1)]


if __name__ == '__main__':
    s = Solution()
    n = 5
    result = s.countBits(n)
    assert result == [0, 1, 1, 2, 1, 2], result
